Various data transfer systems have been developed including storage systems, cellular telephone systems, and radio transmission systems. In each of the systems data is transferred from a sender to a receiver via some medium. For example, in a storage system, data is sent from a sender (i.e., a write function) to a receiver (i.e., a read function) via a storage medium. As information is stored and transmitted in the form of digital data, errors are introduced that, if not corrected, can corrupt the data and render the information unusable. The effectiveness of any transfer is impacted by any losses in data caused by various factors. Many types of error checking systems have been developed to detect and correct errors in digital data. For example, in perhaps the simplest system, a parity bit can be added to a group of data bits, ensuring that the group of data bits (including the parity bit) has either an even or odd number of ones. When using odd parity, as the data is prepared for storage or transmission, the number of data bits in the group that are set to one are counted, and if there is an even number of ones in the group, the parity bit is set to one to ensure that the group has an odd number of ones. If there is an odd number of ones in the group, the parity bit is set to zero to ensure that the group has an odd number of ones. After the data is retrieved from storage or received from transmission, the parity can again be checked, and if the group has an even parity, at least one error has been introduced in the data. At this simplistic level, some errors can be detected but not corrected.
The parity bit may also be used in error correction systems, including in LDPC decoders. An LDPC code is a parity-based code that can be visually represented in a Tanner graph 100 as illustrated in FIG. 1. In an LDPC decoder, multiple parity checks are performed in a number of check nodes 102, 104, 106 and 108 for a group of variable nodes 110, 112, 114, 116, 118, 120, 122, and 124. The connections (or edges) between variable nodes 110-124 and check nodes 102-108 are selected as the LDPC code is designed, balancing the strength of the code against the complexity of the decoder required to execute the LDPC code as data is obtained. The number and placement of parity bits in the group are selected as the LDPC code is designed. Messages are passed between connected variable nodes 110-124 and check nodes 102-108 in an iterative process, passing beliefs about the values that should appear in variable nodes 110-124 to connected check nodes 102-108. Parity checks are performed in the check nodes 102-108 based on the messages and the results are returned to connected variable nodes 110-124 to update the beliefs if necessary. LDPC decoders may be implemented in binary or non-binary fashion. In a binary LDPC decoder, variable nodes 110-124 contain scalar values based on a group of data and parity bits that are retrieved from a storage device, received by a transmission system or obtained in some other way. Messages in the binary LDPC decoders are scalar values transmitted as plain-likelihood probability values or log-likelihood-ratio (LLR) values representing the probability that the sending variable node contains a particular value. In a non-binary LDPC decoder, variable nodes 110-124 contain symbols from a Galois field, a finite field GF(pk) that contains a finite number of elements, characterized by size pk where p is a prime number and k is a positive integer. Messages in the non-binary LDPC decoders are multi-dimensional vectors, generally either plain-likelihood probability vectors or LLR vectors.
The connections between variable nodes 110-124 and check nodes 102-108 may be presented in matrix form as follows, where columns represent variable nodes, rows represent check nodes, and a random non-zero element a(i,j) from the Galois field at the intersection of a variable node column and a check node row indicates a connection between that variable node and check node and provides a permutation for messages between that variable node and check node:
  H  =      [                                        a            ⁡                          (                              1                ,                1                            )                                                0                          0                                      a            ⁡                          (                              1                ,                2                            )                                                0                                      a            ⁡                          (                              1                ,                3                            )                                                            a            ⁡                          (                              1                ,                4                            )                                                0                                      0                                      a            ⁡                          (                              2                ,                1                            )                                                0                          0                                      a            ⁡                          (                              2                ,                2                            )                                                0                          0                                      a            ⁡                          (                              2                ,                3                            )                                                                        a            ⁡                          (                              3                ,                1                            )                                                0                                      a            ⁡                          (                              3                ,                2                            )                                                0                                      a            ⁡                          (                              3                ,                3                            )                                                            a            ⁡                          (                              3                ,                4                            )                                                0                                      a            ⁡                          (                              3                ,                5                            )                                                            0                                      a            ⁡                          (                              4                ,                1                            )                                                0                                      a            ⁡                          (                              4                ,                2                            )                                                0                          0                                      a            ⁡                          (                              4                ,                3                            )                                                            a            ⁡                          (                              4                ,                4                            )                                            ]  
By providing multiple check nodes 102-108 for the group of variable nodes 110-124, redundancy in error checking is provided, enabling errors to be corrected as well as detected. Each check node 102-108 performs a parity check on bits or symbols passed as messages from its neighboring (or connected) variable nodes.
Decoding of binary LDPC codes is typically simplified by making approximations in calculations. However, although non-binary or multi-level LDPC decoders can provide much better error detection and correction performance than binary LDPC decoders, the approximations and simplifications applied in binary LDPC decoders are generally not applicable to multi-level LDPC decoders. A need thus remains for efficient multi-level LDPC decoders.